package xyz.zhno.list;

import java.util.Arrays;
import java.util.Collection;

/**
 * 自定义 List
 * @author zh_o
 * @date 2020-11-17
 */
public class CustomList<E> {

    /**
     * 默认空数组
     */
    private static final Object[] DEFAULT_EMPTY_ARRAY = {};

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 最大容量
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 储存元素数组
     */
    private Object[] elementData;

    /**
     * 元素个数
     */
    private int size;

    /**
     * 修改次数
     */
    private int modCount;



    /**
     * 空参构造
     */
    public CustomList() {
        // 复值空数组
        this.elementData = DEFAULT_EMPTY_ARRAY;
    }

    /**
     * 指定初始化容量构造函数
     * @param initialCapacity 容量
     */
    public CustomList(int initialCapacity) {
        if (initialCapacity > 0) {
            elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            elementData = DEFAULT_EMPTY_ARRAY;
        } else {
            throw new IllegalArgumentException("非法容量: " + initialCapacity);
        }
    }

    /**
     * 传入集合构造
     * @param coll 传入集合
     */
    public CustomList(Collection<? extends E> coll) {
        // 将传入集合转换为数组并赋值到元素数组
        elementData = coll.toArray();
        // 判断数组元素数
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class) {
                elementData = Arrays.copyOf(elementData, size, Object[].class);
            }
        } else {
            elementData = DEFAULT_EMPTY_ARRAY;
        }
    }

    /**
     * 将容量修建到当前元素个数大小
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0) ? DEFAULT_EMPTY_ARRAY : Arrays.copyOf(elementData, size);
        }
    }

    /**
     * 手动扩容
     * @param minCapacity 最小需求容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULT_EMPTY_ARRAY) ? 0 : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    /**
     * 计算容量
     * @param elementData 元素数组
     * @param minCapacity 最小需要容量
     * @return 计算后容量
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULT_EMPTY_ARRAY) {
            // 如果当前的存储元素为空，返回默认容量与最小需要容量中的较大值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 不等于空直接返回传入容量
        return minCapacity;
    }

    /**
     * 明确容量
     * @param minCapacity 最小需求容量
     */
    private void ensureCapacityInternal(int minCapacity) {
        // 判断是否需要扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    /**
     * 明确是否需要扩容
     * @param minCapacity 最小需求容量
     */
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 最小需求容量与当前元素数组长度差 > 0 说明需要扩容
        if (minCapacity - elementData.length > 0) {
            // 调用扩容方法
            grow(minCapacity);
        }
    }

    /**
     * 扩容
     * @param minCapacity 最小需求容量
     */
    private void grow(int minCapacity) {
        // 记录原容量
        int oldCapacity = elementData.length;
        // 如果扩容后容量为原容量 1.5 倍左右（最小需求容量可能为奇数）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果扩容后容量小于原容量
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        // 如果扩容后容量大于最大元素数
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        // 扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 容量大于最大值
     * @param minCapacity 需求容量
     * @return 新的容量
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    /**
     * 获取元素个数
     * @return 元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 访问元素
     * @param index 下标
     * @return 下标对应元素
     */
    @SuppressWarnings("all")
    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 获取指定下标元素
     * @param index 下标
     * @return 对应元素
     */
    public E get(int index) {
        return elementData(index);
    }

    /**
     * 新增元素
     * @param e 元素
     * @return 是否成功
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    /**
     * 是否下标越界
     * @param index 下标
     */
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > this.size) {
            throw new IndexOutOfBoundsException("下标: "+index+", 元素个数: "+this.size);
        }
    }

}
